/**
 * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
 * 二叉树的搜索
 * @param root 
 * @param val 
 */
const searchBST = (root: TreeNode | null, val: number): TreeNode | null => {
    // 为空
    if (root === null) return null;
    // 找到了
    if (root.val === val) return root;

    return searchBST(root.left, val) || searchBST(root.right, val)
};


const searchBST2 = (root: TreeNode | null, val: number): TreeNode | null => {
    // 边界判断
    if (root === null) return null

    let ans: TreeNode | null = null;

    const findTarget = (n: TreeNode | null) => {
        // 节点为空或者找到了结果, 直接返回
        if (n === null || ans !== null) return;

        if (n.val === val) {
            ans = n
            return;
        }

        findTarget(n.left)
        findTarget(n.right)

    }

    findTarget(root)

    return ans
};